
export class AVLNode<T>  {
    // 高度默认是1
    height = 1
    value: T | undefined
    left: AVLNode<T> | null
    right: AVLNode<T> | null
    parent: AVLNode<T> | null
    constructor(value: T, parent: AVLNode<T> | null, left: AVLNode<T> | null, right: AVLNode<T> | null) {
        this.value = value;
        this.parent = parent
        this.left = left;
        this.right = right;
    }

    /**
     * 获取平衡因子
     */
    fac() {
        return this.heightDiff()
    }

    /**
     * 判断当前节点是否平衡
     */
    isBalance() {
        // 高度相减不能超过 1 => -1 <= h <= 1
        return Math.abs(this.heightDiff()) <= 1
    }

    /**
     * 左右子树高度差
     */
    heightDiff() {
        const leftHeight = this.left === null ? 0 : this.left!.height
        const rightHeight = this.right === null ? 0 : this.right!.height
        // 左高度减去右子树高度
        return leftHeight - rightHeight;
    }

    /**
     * 更新当前节点的高度
     */
    updateHeight() {
        const leftHeight = this.left === null ? 0 : this.left!.height
        const rightHeight = this.right === null ? 0 : this.right!.height
        // 左右子树高度差加一
        this.height = 1 + Math.max(leftHeight, rightHeight)
    }

    /**
     * 获取获取该节点最高的孩子
     */
    getTallChild() {
        // 获取高度差
        const isLeftHeight = this.heightDiff();

        if (isLeftHeight > 0) {
            // 左高
            return this.left;
        } else if (isLeftHeight < 0) {
            // 右高
            return this.right;
        } else {
            // 高度一样，返回是左孩子还是右孩子
            return this.isLeft() ? this.left : this.right
        }
    }

    /**
     * p的右孩子
     * @param p 
     */
    isRight(): boolean {
        if (this.parent === null) return false
        return this.parent.right === this
    }

    /**
     * p的左孩子
     * @param p 
     */
    isLeft() {
        if (this.parent === null) return false
        return this.parent.left === this;
    }

    /**
     * 是不是叶子节点
     */
    isLeaf() {
        return this.left == null && this.right == null
    }

    /**
     * 是不是根节点
     */
    isRoot() {
        return this.parent === null
    }

    /**
     * 节点度为2
     */
    hasTwoChild() {
        return this.left !== null && this.right !== null
    }

    /**
     * 节点度为1
     */
    hasOneChild() {
        return (this.left === null && this.right !== null) || (this.left !== null && this.right === null)
    }

    /**
     * 是否有右孩子
     */
    hasRightChild() {
        return this.right !== null
    }

    /**
     * 是否右左孩子
     */
    hasLeftChild() {
        return this.left !== null
    }
}
